{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #力扣泡泡龙"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #dynamic-programming #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #动态规划 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getMaxLayerSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #力扣泡泡龙"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "欢迎各位勇者来到力扣城，本次试炼主题为「力扣泡泡龙」。\n",
    "\n",
    "游戏初始状态的泡泡形如二叉树 `root`，每个节点值对应了该泡泡的分值。勇者最多可以击破一个节点泡泡，要求满足：\n",
    "- 被击破的节点泡泡 **至多** 只有一个子节点泡泡\n",
    "- 当被击破的节点泡泡有子节点泡泡时，则子节点泡泡将取代被击破泡泡的位置\n",
    "    > 注：即整棵子树泡泡上移\n",
    "\n",
    "请问在击破一个节点泡泡操作或无击破操作后，二叉泡泡树的最大「层和」是多少。\n",
    "\n",
    "**注意：**\n",
    "- 「层和」为同一高度的所有节点的分值之和\n",
    "\n",
    "**示例 1：**\n",
    "> 输入：`root = [6,0,3,null,8]`\n",
    ">\n",
    "> 输出：`11`\n",
    ">\n",
    "> 解释：勇者的最佳方案如图所示\n",
    ">![image.png](https://pic.leetcode-cn.com/1648180809-XSWPLu-image.png){:height=\"100px\"}\n",
    "\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    "> 输入：`root = [5,6,2,4,null,null,1,3,5]`\n",
    ">\n",
    "> 输出：`9`\n",
    ">\n",
    "> 解释：勇者击破 6 节点，此时「层和」最大为 3+5+1 = 9\n",
    ">![image.png](https://pic.leetcode-cn.com/1648180769-TLpYop-image.png){:height=\"200px\"}\n",
    "\n",
    "\n",
    "\n",
    "**示例 3：**\n",
    "> 输入：`root = [-5,1,7]`\n",
    ">\n",
    "> 输出：`8`\n",
    ">\n",
    "> 解释：勇者不击破节点，「层和」最大为 1+7 = 8\n",
    "\n",
    "\n",
    "**提示**：\n",
    "- `2 <= 树中节点个数 <= 10^5`\n",
    "- `-10000 <= 树中节点的值 <= 10000`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [WInSav](https://leetcode.cn/problems/WInSav/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [WInSav](https://leetcode.cn/problems/WInSav/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[6,0,3,null,8]', '[5,6,2,4,null,null,1,3,5]', '[-5,1,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getMaxLayerSum(self, root: Optional[TreeNode]) -> int:\n",
    "        # 节点和\n",
    "        d_info = {}\n",
    "\n",
    "        # 可以增加的值\n",
    "        d_add = defaultdict(int)\n",
    "\n",
    "        class Info:\n",
    "            # 最大层数\n",
    "            maxi = -1\n",
    "            # 最大层数个数\n",
    "            lastNum = 0\n",
    "            # 最大层数能增加数量\n",
    "            maxadd = []\n",
    "\n",
    "            def __init__(self, i):\n",
    "                # 层数\n",
    "                self.i = i\n",
    "                # 0：还未判断上下之间关系\n",
    "                # len(l_sum): 已经完成判断\n",
    "                # 其他：当前只需要判断到doi\n",
    "                self.doi = 0\n",
    "                # 最后一层节点数量\n",
    "                self.lastNum = 1\n",
    "                self.l_sum = []\n",
    "\n",
    "        def doOne(n, info):\n",
    "            l_sum = info.l_sum\n",
    "            #print(info.i, l_sum, info.doi)\n",
    "\n",
    "            if info.doi == 0:\n",
    "                info.doi = len(l_sum) - 1\n",
    "                maxi = info.i + len(l_sum)\n",
    "                if maxi > Info.maxi:\n",
    "                    if Info.maxadd:\n",
    "                        d_add[Info.maxi - 1] = max(d_add[Info.maxi - 1], -Info.maxadd[0][0])\n",
    "\n",
    "                    Info.maxi = maxi\n",
    "                    Info.lastNum = info.lastNum\n",
    "\n",
    "                    if l_sum[-1] < 0:\n",
    "                        Info.maxadd = [(l_sum[-1], info.lastNum)]\n",
    "                    else:\n",
    "                        Info.maxadd = []\n",
    "                elif maxi == Info.maxi:\n",
    "                    Info.lastNum = max(Info.lastNum, info.lastNum)\n",
    "\n",
    "                    if info.l_sum[-1] < 0:\n",
    "                        bisect.insort(Info.maxadd, (l_sum[-1], info.lastNum))\n",
    "                        del Info.maxadd[2:]\n",
    "                elif l_sum[-1] < 0:\n",
    "                    d_add[maxi - 1] = max(d_add[maxi - 1], -l_sum[-1])\n",
    "\n",
    "            for i in range(info.doi):\n",
    "                cha = l_sum[i + 1] - l_sum[i]\n",
    "                if cha > 0 and cha > d_add[info.i + i]:\n",
    "                    #print(info.i + i, cha)\n",
    "                    d_add[info.i + i] = cha\n",
    "\n",
    "            info.doi = len(l_sum)\n",
    "            d_info[id(n)] = info\n",
    "\n",
    "        def doEnd(info):\n",
    "            Info.lastNum = info.lastNum\n",
    "            l_sum = info.l_sum\n",
    "            ret = max(l_sum)\n",
    "\n",
    "            for i, add in d_add.items():\n",
    "                ret = max(ret, l_sum[i] + add)\n",
    "\n",
    "            for add, num in Info.maxadd:\n",
    "                if num != Info.lastNum:\n",
    "                    ret = max(ret, l_sum[-1] - add)\n",
    "                    break\n",
    "\n",
    "            return ret\n",
    "\n",
    "        # 递归层数超，修改为非递归\n",
    "        dp = [[root, None, Info(0)]]\n",
    "\n",
    "        while 1:\n",
    "            n, p, info = dp[-1]\n",
    "            i = info.i\n",
    "            l_sum = info.l_sum\n",
    "\n",
    "            _n = n\n",
    "\n",
    "            if not l_sum:\n",
    "                l_sum.append(n.val)\n",
    "\n",
    "                while 1:\n",
    "                    if not n.left and not n.right:\n",
    "                        # 单节点到底\n",
    "                        if not p:\n",
    "                            return doEnd(info)\n",
    "\n",
    "                        doOne(_n, info)\n",
    "                        dp.pop()\n",
    "                        break\n",
    "\n",
    "                    if n.left and n.right:\n",
    "                        # 双节点到底\n",
    "                        _n.left, _n.right = n.left, n.right\n",
    "                        dp.append((n.left, n, Info(i + 1)))\n",
    "                        dp.append((n.right, n, Info(i + 1)))\n",
    "                        break\n",
    "\n",
    "                    i += 1\n",
    "                    n = n.left or n.right\n",
    "                    l_sum.append(n.val)\n",
    "            else:\n",
    "                # 左右节点都计算完成\n",
    "                left = d_info.pop(id(n.left))\n",
    "                right = d_info.pop(id(n.right))\n",
    "\n",
    "                # nn大于1才能删除，这时需要判断上下大小关系\n",
    "                nn = len(l_sum)\n",
    "                nl = len(left.l_sum)\n",
    "                nr = len(right.l_sum)\n",
    "\n",
    "                if nl > nr:\n",
    "                    info.lastNum = left.lastNum\n",
    "                    if left.doi == 0:\n",
    "                        info.doi = 0\n",
    "                    elif left.doi == nl:\n",
    "                        info.doi = nr + nn\n",
    "                    else:\n",
    "                        info.doi = max(left.doi, nr) + nn\n",
    "                elif nl == nr:\n",
    "                    info.lastNum = left.lastNum + right.lastNum\n",
    "                    info.doi = 0\n",
    "                else:\n",
    "                    info.lastNum = right.lastNum\n",
    "                    if right.doi == 0:\n",
    "                        info.doi = 0\n",
    "                    elif right.doi == nr:\n",
    "                        info.doi = nl + nn\n",
    "                    else:\n",
    "                        info.doi = max(right.doi, nl) + nn\n",
    "\n",
    "                if nl >= nr:\n",
    "                    for i, v in enumerate(right.l_sum):\n",
    "                        left.l_sum[i] += v\n",
    "                    l_sum += left.l_sum\n",
    "                else:\n",
    "                    for i, v in enumerate(left.l_sum):\n",
    "                        right.l_sum[i] += v\n",
    "                    l_sum += right.l_sum\n",
    "\n",
    "                if p:\n",
    "                    if nn > 1:\n",
    "                        doOne(n, info)\n",
    "                    else:\n",
    "                        d_info[id(n)] = info\n",
    "                    dp.pop()\n",
    "                else:\n",
    "                    return doEnd(info)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getMaxLayerSum(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node):\n",
    "            if node.left is None and node.right is None:\n",
    "                return [node.val], [node.val], 0, True\n",
    "            elif node.left is None or node.right is None:\n",
    "                child = node.left or node.right\n",
    "                nohit, hit, move_up_range, last_null = dfs(child)\n",
    "                nohit.append(node.val)\n",
    "                hit.append(node.val)\n",
    "                for i in range(-1, -1 - move_up_range, -1):\n",
    "                    hit[i] = max(hit[i], nohit[i - 1])\n",
    "                if len(hit) - 1 - move_up_range > 0:\n",
    "                    hit[len(hit) - 1 - move_up_range] = max(hit[len(hit) - 1 - move_up_range], nohit[len(hit) - 2 - move_up_range])\n",
    "                #print(\"dfs1\", node.val, nohit, hit)\n",
    "                return nohit, hit, 0, True\n",
    "            else:\n",
    "                left_result = dfs(node.left)\n",
    "                right_result = dfs(node.right)\n",
    "                if len(left_result[0]) < len(right_result[0]):\n",
    "                    left_result, right_result = right_result, left_result\n",
    "                nohit_left, hit_left, move_up_range_left, last_null_left = left_result\n",
    "                nohit_right, hit_right, _, last_null_right = right_result\n",
    "                for i in range(len(hit_right)):\n",
    "                    hr = hit_right[i]\n",
    "                    if i == 0 and last_null_right:\n",
    "                        hr = max(hr, 0)\n",
    "                    j = len(hit_left) - len(hit_right) + i\n",
    "                    hl = hit_left[j]\n",
    "                    if j == 0 and last_null_left:\n",
    "                        hl = max(hl, 0)\n",
    "                    hit_left[j] = max(hl + nohit_right[i], nohit_left[j] + hr)\n",
    "                for i in range(len(nohit_right)):\n",
    "                    j = len(hit_left) - len(hit_right) + i\n",
    "                    nohit_left[j] += nohit_right[i]\n",
    "                last_null = (len(hit_left) > len(hit_right)) and last_null_left\n",
    "                nohit_left.append(node.val)\n",
    "                hit_left.append(node.val)\n",
    "                move_up_range = max(move_up_range_left, len(nohit_right)) + 1\n",
    "                #print(\"dfs2\", node.val, nohit_left, hit_left, move_up_range, last_null)\n",
    "                return nohit_left, hit_left, move_up_range, last_null\n",
    "\n",
    "        _, hit, _, _ = dfs(root)\n",
    "        return max(hit)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getMaxLayerSum(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node):\n",
    "            if node.left is None and node.right is None:\n",
    "                return [node.val], [node.val], 0, True\n",
    "            elif node.left is None or node.right is None:\n",
    "                child = node.left or node.right\n",
    "                nohit, hit, move_up_range, last_null = dfs(child)\n",
    "                nohit.append(node.val)\n",
    "                hit.append(node.val)\n",
    "                for i in range(-1, -1 - move_up_range, -1):\n",
    "                    hit[i] = max(hit[i], nohit[i - 1])\n",
    "                if len(hit) - 1 - move_up_range > 0:\n",
    "                    hit[len(hit) - 1 - move_up_range] = max(hit[len(hit) - 1 - move_up_range], nohit[len(hit) - 2 - move_up_range])\n",
    "                #print(\"dfs1\", node.val, nohit, hit)\n",
    "                return nohit, hit, 0, True\n",
    "            else:\n",
    "                left_result = dfs(node.left)\n",
    "                right_result = dfs(node.right)\n",
    "                if len(left_result[0]) < len(right_result[0]):\n",
    "                    left_result, right_result = right_result, left_result\n",
    "                nohit_left, hit_left, move_up_range_left, last_null_left = left_result\n",
    "                nohit_right, hit_right, _, last_null_right = right_result\n",
    "                for i in range(len(hit_right)):\n",
    "                    hr = hit_right[i]\n",
    "                    if i == 0 and last_null_right:\n",
    "                        hr = max(hr, 0)\n",
    "                    j = len(hit_left) - len(hit_right) + i\n",
    "                    hl = hit_left[j]\n",
    "                    if j == 0 and last_null_left:\n",
    "                        hl = max(hl, 0)\n",
    "                    hit_left[j] = max(hl + nohit_right[i], nohit_left[j] + hr)\n",
    "                for i in range(len(nohit_right)):\n",
    "                    j = len(hit_left) - len(hit_right) + i\n",
    "                    nohit_left[j] += nohit_right[i]\n",
    "                last_null = (len(hit_left) > len(hit_right)) and last_null_left\n",
    "                nohit_left.append(node.val)\n",
    "                hit_left.append(node.val)\n",
    "                move_up_range = max(move_up_range_left, len(nohit_right)) + 1\n",
    "                #print(\"dfs2\", node.val, nohit_left, hit_left, move_up_range, last_null)\n",
    "                return nohit_left, hit_left, move_up_range, last_null\n",
    "\n",
    "        _, hit, _, _ = dfs(root)\n",
    "        return max(hit)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.left = None\r\n",
    "#         self.right = None\r\n",
    "class Solution:\r\n",
    "    def getMaxLayerSum(self, root: Optional[TreeNode]) -> int:\r\n",
    "        def dfs(node):\r\n",
    "            if node.left is None and node.right is None:\r\n",
    "                return [node.val], [node.val], 0, True\r\n",
    "            elif node.left is None or node.right is None:\r\n",
    "                child = node.left or node.right\r\n",
    "                nohit, hit, move_up_range, last_null = dfs(child)\r\n",
    "                nohit.append(node.val)\r\n",
    "                hit.append(node.val)\r\n",
    "                for i in range(-1, -1 - move_up_range, -1):\r\n",
    "                    hit[i] = max(hit[i], nohit[i - 1])\r\n",
    "                if len(hit) - 1 - move_up_range > 0:\r\n",
    "                    hit[len(hit) - 1 - move_up_range] = max(hit[len(hit) - 1 - move_up_range], nohit[len(hit) - 2 - move_up_range])\r\n",
    "                #print(\"dfs1\", node.val, nohit, hit)\r\n",
    "                return nohit, hit, 0, True\r\n",
    "            else:\r\n",
    "                left_result = dfs(node.left)\r\n",
    "                right_result = dfs(node.right)\r\n",
    "                if len(left_result[0]) < len(right_result[0]):\r\n",
    "                    left_result, right_result = right_result, left_result\r\n",
    "                nohit_left, hit_left, move_up_range_left, last_null_left = left_result\r\n",
    "                nohit_right, hit_right, _, last_null_right = right_result\r\n",
    "                for i in range(len(hit_right)):\r\n",
    "                    hr = hit_right[i]\r\n",
    "                    if i == 0 and last_null_right:\r\n",
    "                        hr = max(hr, 0)\r\n",
    "                    j = len(hit_left) - len(hit_right) + i\r\n",
    "                    hl = hit_left[j]\r\n",
    "                    if j == 0 and last_null_left:\r\n",
    "                        hl = max(hl, 0)\r\n",
    "                    hit_left[j] = max(hl + nohit_right[i], nohit_left[j] + hr)\r\n",
    "                for i in range(len(nohit_right)):\r\n",
    "                    j = len(hit_left) - len(hit_right) + i\r\n",
    "                    nohit_left[j] += nohit_right[i]\r\n",
    "                last_null = (len(hit_left) > len(hit_right)) and last_null_left\r\n",
    "                nohit_left.append(node.val)\r\n",
    "                hit_left.append(node.val)\r\n",
    "                move_up_range = max(move_up_range_left, len(nohit_right)) + 1\r\n",
    "                #print(\"dfs2\", node.val, nohit_left, hit_left, move_up_range, last_null)\r\n",
    "                return nohit_left, hit_left, move_up_range, last_null\r\n",
    "\r\n",
    "        _, hit, _, _ = dfs(root)\r\n",
    "        return max(hit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getMaxLayerSum(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node):\n",
    "            if node.left is None and node.right is None:\n",
    "                return [node.val],[node.val],0,True\n",
    "            elif node.left is None or node.right is None:\n",
    "                child=node.left or node.right\n",
    "                nohit,hit,move_up_range,last_null=dfs(child)\n",
    "                nohit.append(node.val)\n",
    "                hit.append(node.val)\n",
    "                for i in range(-1,-1-move_up_range,-1):\n",
    "                    hit[i]=max(hit[i],nohit[i-1])\n",
    "                if len(hit)-1-move_up_range>0:\n",
    "                    hit[len(hit)-1-move_up_range]=max(hit[len(hit)-1-move_up_range],nohit[len(hit)-2-move_up_range])\n",
    "                return nohit,hit,0,True\n",
    "            else:\n",
    "                left_result=dfs(node.left)\n",
    "                right_result=dfs(node.right)\n",
    "                if len(left_result[0])<len(right_result[0]):\n",
    "                    left_result,right_result=right_result,left_result\n",
    "                nohit_left,hit_left,move_up_range_left,last_null_left=left_result\n",
    "                nohit_right,hit_right,_,last_null_right=right_result\n",
    "                for i in range(len(hit_right)):\n",
    "                    hr=hit_right[i]\n",
    "                    if i ==0 and last_null_right:\n",
    "                        hr=max(hr,0)\n",
    "                    j=len(hit_left)-len(hit_right)+i\n",
    "                    hl=hit_left[j]\n",
    "                    if j==0 and last_null_left:\n",
    "                        hl=max(hl,0)\n",
    "                    hit_left[j]=max(hl+nohit_right[i],hr+nohit_left[j])\n",
    "                for i in range(len(nohit_right)):\n",
    "                    j=len(hit_left)-len(hit_right)+i\n",
    "                    nohit_left[j]+=nohit_right[i]\n",
    "                last_null=(len(hit_left)>len(hit_right)) and last_null_left\n",
    "                nohit_left.append(node.val)\n",
    "                hit_left.append(node.val)\n",
    "                move_up_range=max(move_up_range_left,len(nohit_right))+1\n",
    "                return nohit_left,hit_left,move_up_range,last_null\n",
    "        _,hit,_,_=dfs(root)\n",
    "        return max(hit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "\tdef getMaxLayerSum(self, root):\n",
    "\t\ths = [] #全树层和\n",
    "\t\thc = [] #全树层节点个数, 用来判断是否消除后变为空行(否则可能结果应为负数, 但得到空行对应的0)\n",
    "\t\tstack = [root]\n",
    "\t\twhile stack:\n",
    "\t\t\ts = 0\n",
    "\t\t\tc = 0\n",
    "\t\t\tnxt = []\n",
    "\t\t\tfor node in stack:\n",
    "\t\t\t\ts += node.val\n",
    "\t\t\t\tc += 1\n",
    "\t\t\t\tif node.left:\n",
    "\t\t\t\t\tnxt.append(node.left)\n",
    "\t\t\t\tif node.right:\n",
    "\t\t\t\t\tnxt.append(node.right)\n",
    "\t\t\ths.append(s)\n",
    "\t\t\thc.append(c)\n",
    "\t\t\tstack = nxt\n",
    "\t\tself.ans = max(hs) #不消除\n",
    "\t\tself.dfs(root, 0, hs, hc)\n",
    "\t\treturn self.ans\n",
    "\t\n",
    "\tdef dfs(self, root, h, hs, hc):\n",
    "\t\tn = 0\n",
    "\t\tif root.left:\n",
    "\t\t\tn += 1\n",
    "\t\t\tsl, cl, hl, mil = self.dfs(root.left, h + 1, hs, hc)\n",
    "\t\telse:\n",
    "\t\t\thl = h\n",
    "\t\t\tmil = h\n",
    "\t\tif root.right:\n",
    "\t\t\tn += 1\n",
    "\t\t\tsr, cr, hr, mir = self.dfs(root.right, h + 1, hs, hc)\n",
    "\t\telse:\n",
    "\t\t\tsr = {} #可能是叶子节点, 赋空值后面无须区分0/1个子节点\n",
    "\t\t\tcr = {}\n",
    "\t\t\thr = h\n",
    "\t\t\tmir = h\n",
    "\t\tif n != 2:\n",
    "\t\t\tres = sl if root.left else sr\n",
    "\t\t\tcnt = cl if root.left else cr\n",
    "\t\t\tres[h] = root.val\n",
    "\t\t\tcnt[h] = 1\n",
    "\t\t\tfor i in range(h, max(mil, mir) + 1): #i取所有\n",
    "\t\t\t\tif hc[i] == cnt[i]: #其它子树此高度已无节点\n",
    "\t\t\t\t\tbreak\n",
    "\t\t\t\tif i + 1 not in res: #其它子树下移至比该子树高\n",
    "\t\t\t\t\tself.ans = max(self.ans, hs[i] - res[i])\n",
    "\t\t\t\t\tbreak\n",
    "\t\t\t\tself.ans = max(self.ans, hs[i] - res[i] + res[i + 1]) #其它子树与该子树错位和\n",
    "\t\t\tmi = h #该节点可消除, 如父节点可消除, 该子树所有高度均无须重复计算\n",
    "\t\telse: \n",
    "\t\t\tif hl >= hr:\n",
    "\t\t\t\tres = sl\n",
    "\t\t\t\tcnt = cl\n",
    "\t\t\t\ts2 = sr\n",
    "\t\t\t\tc2 = cr\n",
    "\t\t\telse:\n",
    "\t\t\t\tres = sr\n",
    "\t\t\t\tcnt = cr\n",
    "\t\t\t\ts2 = sl\n",
    "\t\t\t\tc2 = cl\n",
    "\t\t\tres[h] = root.val\n",
    "\t\t\tcnt[h] = 1\n",
    "\t\t\tfor key in s2:\n",
    "\t\t\t\tres[key] = res.get(key, 0) + s2[key]\n",
    "\t\t\t\tcnt[key] = cnt.get(key, 0) + c2[key]\n",
    "\t\t\tmi = max(mil, mir, min(hl, hr)) #该节点不可消除, 须遍历深度为max(两子树应遍历未遍历(不可消除), 合并该节点左右子树导致的层和变化(即max(hl, hr)))\n",
    "\t\treturn res, cnt, max(hl, hr), mi #已遍历层和, 层节点数, 子树深度(原树高度), 子树须错位的最深处\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "\tdef getMaxLayerSum(self, root):\n",
    "\t\ths = []\n",
    "\t\thc = []\n",
    "\t\tstack = [root]\n",
    "\t\twhile stack:\n",
    "\t\t\ts = 0\n",
    "\t\t\tc = 0\n",
    "\t\t\tnxt = []\n",
    "\t\t\tfor node in stack:\n",
    "\t\t\t\ts += node.val\n",
    "\t\t\t\tc += 1\n",
    "\t\t\t\tif node.left:\n",
    "\t\t\t\t\tnxt.append(node.left)\n",
    "\t\t\t\tif node.right:\n",
    "\t\t\t\t\tnxt.append(node.right)\n",
    "\t\t\ths.append(s)\n",
    "\t\t\thc.append(c)\n",
    "\t\t\tstack = nxt\n",
    "\t\tself.ans = max(hs)\n",
    "\t\tself.dfs(root, 0, hs, hc)\n",
    "\t\treturn self.ans\n",
    "\t\n",
    "\tdef dfs(self, root, h, hs, hc):\n",
    "\t\tn = 0\n",
    "\t\tif root.left:\n",
    "\t\t\tn += 1\n",
    "\t\t\tsl, cl, hl, mil = self.dfs(root.left, h + 1, hs, hc)\n",
    "\t\telse:\n",
    "\t\t\thl = h\n",
    "\t\t\tmil = h\n",
    "\t\tif root.right:\n",
    "\t\t\tn += 1\n",
    "\t\t\tsr, cr, hr, mir = self.dfs(root.right, h + 1, hs, hc)\n",
    "\t\telse:\n",
    "\t\t\tsr = {}\n",
    "\t\t\tcr = {}\n",
    "\t\t\thr = h\n",
    "\t\t\tmir = h\n",
    "\t\tif n != 2:\n",
    "\t\t\tres = sl if root.left else sr\n",
    "\t\t\tcnt = cl if root.left else cr\n",
    "\t\t\tres[h] = root.val\n",
    "\t\t\tcnt[h] = 1\n",
    "\t\t\t#if flag == False: #打破该节点, 等价于其它子树下移; 如果父节点也可以被打破, 该节点不重复计算\n",
    "\t\t\tfor i in range(h, max(mil, mir) + 1): #i取所有\n",
    "\t\t\t\tif hc[i] == cnt[i]: #其它子树此高度已无节点\n",
    "\t\t\t\t\tbreak\n",
    "\t\t\t\tif i + 1 not in res: #其它子树下移至比该子树高\n",
    "\t\t\t\t\tself.ans = max(self.ans, hs[i] - res[i])\n",
    "\t\t\t\t\tbreak\n",
    "\t\t\t\tself.ans = max(self.ans, hs[i] - res[i] + res[i + 1]) #其它子树与该子树错位和\n",
    "\t\t\tmi = h #res值变化的最深行, 更深的行无变化, 之前遍历已计算过, 不重复计算\n",
    "\t\telse: \n",
    "\t\t\tif hl >= hr:\n",
    "\t\t\t\tres = sl\n",
    "\t\t\t\tcnt = cl\n",
    "\t\t\t\ts2 = sr\n",
    "\t\t\t\tc2 = cr\n",
    "\t\t\telse:\n",
    "\t\t\t\tres = sr\n",
    "\t\t\t\tcnt = cr\n",
    "\t\t\t\ts2 = sl\n",
    "\t\t\t\tc2 = cl\n",
    "\t\t\tres[h] = root.val\n",
    "\t\t\tcnt[h] = 1\n",
    "\t\t\tfor key in s2:\n",
    "\t\t\t\tres[key] = res.get(key, 0) + s2[key]\n",
    "\t\t\t\tcnt[key] = cnt.get(key, 0) + c2[key]\n",
    "\t\t\tmi = max(mil, mir, min(hl, hr))\n",
    "\t\treturn res, cnt, max(hl, hr), mi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getMaxLayerSum(self, root: Optional[TreeNode]) -> int:\n",
    "        \"\"\"\n",
    "        :type root: Optional[TreeNode]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        level_sum = []\n",
    "        level_size = []\n",
    "\n",
    "        q = [root]\n",
    "        head = 0\n",
    "        tail = 1\n",
    "        while head < tail:\n",
    "            level_sum.append(0)\n",
    "            level_size.append(tail - head)\n",
    "            for now in q[head : tail]:\n",
    "                level_sum[-1] += now.val\n",
    "                if now.left:\n",
    "                    q.append(now.left)\n",
    "                if now.right:\n",
    "                    q.append(now.right)\n",
    "            \n",
    "            head, tail = tail, len(q)\n",
    "        \n",
    "        global res\n",
    "        res = max(level_sum)\n",
    "        \n",
    "        delta = {}\n",
    "        need_refresh = {}\n",
    "        remove_size = {}\n",
    "\n",
    "        def dfs(now, level):\n",
    "            global res\n",
    "            if now.left is None:\n",
    "                if now.right is None:\n",
    "                    remove_size[now] = {level: 1}\n",
    "                    need_refresh[now] = set()\n",
    "                    if level_size[level] == 1:\n",
    "                        delta[now] = {}\n",
    "                    else:\n",
    "                        delta[now] = {level: -now.val}\n",
    "                        res = max(res, level_sum[level] + delta[now][level])\n",
    "                else:\n",
    "                    dfs(now.right, level + 1)\n",
    "                    delta[now] = delta[now.right]\n",
    "                    delta[now][level] = now.right.val - now.val\n",
    "                    remove_size[now] = remove_size[now.right]\n",
    "                    remove_size[now][level] = 1\n",
    "                    need_refresh[now] = need_refresh[now.right]\n",
    "                    need_refresh[now].add(level)\n",
    "\n",
    "                    for lv in need_refresh[now]:\n",
    "                        if remove_size[now][lv] < level_size[lv]:\n",
    "                            res = max(res, level_sum[lv] + delta[now][lv])\n",
    "                    need_refresh[now] = set()\n",
    "\n",
    "            elif now.right is None:\n",
    "                dfs(now.left, level + 1)\n",
    "                delta[now] = delta[now.left]\n",
    "                delta[now][level] = now.left.val - now.val\n",
    "                remove_size[now] = remove_size[now.left]\n",
    "                remove_size[now][level] = 1\n",
    "                need_refresh[now] = need_refresh[now.left]\n",
    "                need_refresh[now].add(level)\n",
    "\n",
    "                for lv in need_refresh[now]:\n",
    "                    if remove_size[now][lv] < level_size[lv]:\n",
    "                        res = max(res, level_sum[lv] + delta[now][lv])\n",
    "                need_refresh[now] = set()\n",
    "            \n",
    "            else:\n",
    "                dfs(now.left, level + 1)\n",
    "                dfs(now.right, level + 1)\n",
    "                \n",
    "                if len(need_refresh[now.left]) > len(need_refresh[now.right]):\n",
    "                    refresh_min, refresh_max = need_refresh[now.right], need_refresh[now.left]\n",
    "                else:\n",
    "                    refresh_min, refresh_max = need_refresh[now.left], need_refresh[now.right]\n",
    "                \n",
    "                need_refresh[now] = refresh_max\n",
    "                for lv in refresh_min:\n",
    "                    need_refresh[now].add(lv)\n",
    "                need_refresh[now].add(level)\n",
    "\n",
    "                if len(delta[now.left]) > len(delta[now.right]):\n",
    "                    delta_min, delta_max = delta[now.right], delta[now.left]\n",
    "                else:\n",
    "                    delta_min, delta_max = delta[now.left], delta[now.right]\n",
    "                \n",
    "                delta[now] = delta_max\n",
    "                for lv in delta_min:\n",
    "                    delta[now][lv] = delta[now].get(lv, 0) + delta_min[lv]\n",
    "                    need_refresh[now].add(lv)\n",
    "                delta[now][level] = now.left.val + now.right.val - now.val\n",
    "                \n",
    "\n",
    "                if len(remove_size[now.left]) > len(remove_size[now.right]):\n",
    "                    remove_min, remove_max = remove_size[now.right], remove_size[now.left]\n",
    "                else:\n",
    "                    remove_min, remove_max = remove_size[now.left], remove_size[now.right]\n",
    "                \n",
    "                remove_size[now] = remove_max\n",
    "                for lv in remove_min:\n",
    "                    remove_size[now][lv] += remove_min[lv]\n",
    "                remove_size[now][level] = 1\n",
    "\n",
    "        dfs(root, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def getMaxLayerSum(self, root: Optional[TreeNode]) -> int:\n",
    "        \"\"\"\n",
    "        :type root: Optional[TreeNode]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        level_sum = []\n",
    "        level_size = []\n",
    "\n",
    "        q = [root]\n",
    "        head = 0\n",
    "        tail = 1\n",
    "        while head < tail:\n",
    "            level_sum.append(0)\n",
    "            level_size.append(tail - head)\n",
    "            for now in q[head : tail]:\n",
    "                level_sum[-1] += now.val\n",
    "                if now.left:\n",
    "                    q.append(now.left)\n",
    "                if now.right:\n",
    "                    q.append(now.right)\n",
    "            \n",
    "            head, tail = tail, len(q)\n",
    "        \n",
    "        global res\n",
    "        res = max(level_sum)\n",
    "        \n",
    "        delta = {}\n",
    "        need_refresh = {}\n",
    "        remove_size = {}\n",
    "\n",
    "        def dfs(now, level):\n",
    "            global res\n",
    "            if now.left is None:\n",
    "                if now.right is None:\n",
    "                    remove_size[now] = {level: 1}\n",
    "                    need_refresh[now] = set()\n",
    "                    if level_size[level] == 1:\n",
    "                        delta[now] = {}\n",
    "                    else:\n",
    "                        delta[now] = {level: -now.val}\n",
    "                        res = max(res, level_sum[level] + delta[now][level])\n",
    "                else:\n",
    "                    dfs(now.right, level + 1)\n",
    "                    delta[now] = delta[now.right]\n",
    "                    delta[now][level] = now.right.val - now.val\n",
    "                    remove_size[now] = remove_size[now.right]\n",
    "                    remove_size[now][level] = 1\n",
    "                    need_refresh[now] = need_refresh[now.right]\n",
    "                    need_refresh[now].add(level)\n",
    "\n",
    "                    for lv in need_refresh[now]:\n",
    "                        if remove_size[now][lv] < level_size[lv]:\n",
    "                            res = max(res, level_sum[lv] + delta[now][lv])\n",
    "                    need_refresh[now] = set()\n",
    "\n",
    "            elif now.right is None:\n",
    "                dfs(now.left, level + 1)\n",
    "                delta[now] = delta[now.left]\n",
    "                delta[now][level] = now.left.val - now.val\n",
    "                remove_size[now] = remove_size[now.left]\n",
    "                remove_size[now][level] = 1\n",
    "                need_refresh[now] = need_refresh[now.left]\n",
    "                need_refresh[now].add(level)\n",
    "\n",
    "                for lv in need_refresh[now]:\n",
    "                    if remove_size[now][lv] < level_size[lv]:\n",
    "                        res = max(res, level_sum[lv] + delta[now][lv])\n",
    "                need_refresh[now] = set()\n",
    "            \n",
    "            else:\n",
    "                dfs(now.left, level + 1)\n",
    "                dfs(now.right, level + 1)\n",
    "                \n",
    "                if len(need_refresh[now.left]) > len(need_refresh[now.right]):\n",
    "                    refresh_min, refresh_max = need_refresh[now.right], need_refresh[now.left]\n",
    "                else:\n",
    "                    refresh_min, refresh_max = need_refresh[now.left], need_refresh[now.right]\n",
    "                \n",
    "                need_refresh[now] = refresh_max\n",
    "                for lv in refresh_min:\n",
    "                    need_refresh[now].add(lv)\n",
    "                need_refresh[now].add(level)\n",
    "\n",
    "                if len(delta[now.left]) > len(delta[now.right]):\n",
    "                    delta_min, delta_max = delta[now.right], delta[now.left]\n",
    "                else:\n",
    "                    delta_min, delta_max = delta[now.left], delta[now.right]\n",
    "                \n",
    "                delta[now] = delta_max\n",
    "                for lv in delta_min:\n",
    "                    delta[now][lv] = delta[now].get(lv, 0) + delta_min[lv]\n",
    "                    need_refresh[now].add(lv)\n",
    "                delta[now][level] = now.left.val + now.right.val - now.val\n",
    "                \n",
    "\n",
    "                if len(remove_size[now.left]) > len(remove_size[now.right]):\n",
    "                    remove_min, remove_max = remove_size[now.right], remove_size[now.left]\n",
    "                else:\n",
    "                    remove_min, remove_max = remove_size[now.left], remove_size[now.right]\n",
    "                \n",
    "                remove_size[now] = remove_max\n",
    "                for lv in remove_min:\n",
    "                    remove_size[now][lv] += remove_min[lv]\n",
    "                remove_size[now][level] = 1\n",
    "\n",
    "        dfs(root, 0)\n",
    "        return res\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
